/*
 * @lc app=leetcode.cn id=2045 lang=typescript
 *
 * [2045] 到达目的地的第二短时间
 */

// @lc code=start
function secondMinimum(n: number, edges: number[][], time: number, change: number): number {
  // 建模
  const graph: number[][] = new Array(n + 1).fill(0).map(() => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  // 计算最短路径和次短路径
  // path[i][0]表示最短路径，path[i][1]表示次短路径
  const path = new Array(n + 1).fill(0).map(() => new Array(2).fill(Number.POSITIVE_INFINITY));
  path[1][0] = 0;
  // 队列，存入[节点，距离]
  const queue: number[][] = [[1, 0]];
  while (path[n][1] === Number.POSITIVE_INFINITY) {
    const [cur, len] = queue.shift();
    for (const next of graph[cur]) {
      if (len + 1 < path[next][0]) {
        path[next][0] = len + 1;
        queue.push([next, len + 1]);
      } else if (len + 1 > path[next][0] && len + 1 < path[next][1]) {
        path[next][1] = len + 1;
        queue.push([next, len + 1]);
      }
    }
    console.log(queue);
  }

  // 计算次短路径所需时间
  let ans = 0;
  for (let i = 0; i < path[n][1]; i++) {
    if (ans % (2 * change) >= change) {
      ans += 2 * change - (ans % (2 * change));
    }
    ans += time;
  }
  return ans;
}
// @lc code=end
